This invention relates to explaining data representing physical objects by a model of those objects through a probability method of analysis.
Multidimensional data can be collected by means of many different physical processes, for example: images may be collected by a video camera; by radar systems; by sonar systems; by infrared systems; by astronomical observations of star systems; by medical imaging using x-rays with dynamic image recording, magnetic resonance imaging, ultrasound, images of the Earth by satellite imagery, or by any other technology capable of generating an image of physical objects. The image data may then be analyzed in order to track targets of interest. Tracking is the recursive estimation of a sequence of states that best explains a sequence of observations. The states are specifications of the configuration of a model which is designed to explain the observations.
As an example, in tracking a human figure in a sequence of video frames a human xe2x80x9cstick modelxe2x80x9d can be used. A line having both length and orientation can be used to represent each major skeletal bone such as lower arm, upper arm, lower leg, upper leg, trunk, head, shoulder girdle, etc. A particular frame of the video can be specified by giving the length, position, and orientation of each of the lines used in the stick model. The xe2x80x9cstatexe2x80x9d is the collection of data required to completely specify the model. The state is used to compute a predicted image in the next video frame, and the recursive estimation process is used to refine the state values by comparing the predicted image with the data gathered by the video camera. As a further example, radar, acoustic, x-ray, etc. data can be used to generate images of the physical objects being observed, and a model of the objects can be used to aid in computation of a predicted image. The state is the set of data required to completely specify the model, for example the location of each aircraft in a radar produced-image for air traffic control purposes.
Modem detectors often return a very large amount of data. For example, a simple video camera produces approximately 30 flames per second (depending on the video protocol) with each frame having approximately 300 pixels horizontally across the image and 200 rows of pixels vertically in the image to yield 60,000 pixels in each image (again the details depending upon the video protocol). It is a very computation intensive process to generate a predicted image for each frame and to compare the predicted image with the actual data in order to refine the state of a model for tracking purposes.
Kalman filter tracking has been successful as a tool for refining the parameters of a model in cases where a probability density function is sufficiently simple. Kalman filters are described by Eli Brookner in the book Tracking and Kalman Filtering Made Easy, published by John Wiley and Sons, Inc., in 1998, all disclosures of which are incorporated herein by reference. However, as data gathered by detectors becomes more complex, and the complex data requires the models to distinguish between ambiguous representations of the data, the simple approach to tracking by Kalman filtering breaks down.
There is needed an improved method for refining the state of a model of objects, where predictions of the model are compared with the large amounts of data produced by modern detectors.
The invention recognizes that a probability density function for fitting a model to a complex set of data often has multiple modes, each mode representing a reasonably probable state of the model when compared with the data. Particularly, sequential data such as are collected from detection of moving objects in three dimensional space are placed into data frames. Also, a single frame of data may require analysis by a sequence of analysis operations. Computation of the probability density function of the model state involves two main stages: (1) state prediction, in which the prior probability distribution is generated from information known prior to the availability of the data, and (2) state update, in which the posterior probability distribution is formed by updating the prior distribution with information obtained from observing the data. In particular this information obtained purely from data observations can also be expressed as a probability density function, known as the likelihood function. The likelihood function is a multimodal (multiple peaks) function when a single data frame leads to multiple distinct measurements from which the correct measurement associated with the model cannot be distinguished. The invention analyzes a multimodal likelihood function by numerically searching the likelihood function for peaks. The numerical search proceeds by randomly sampling from the prior distribution to select a number of seed points in state-space, and then numerically finding the maxima of the likelihood function starting from each seed point. Furthermore, kernel functions are fitted to these peaks to represent the likelihood function as an analytic function. The resulting posterior distribution is also multimodal and represented using a set of kernel functions. It is computed by combining the prior distribution and the likelihood function using Bayes Rule. The peaks in the posterior distribution are also referred to as xe2x80x98hypothesesxe2x80x99, as they are hypotheses for the states of the model which best explain both the data and the prior knowledge.
The invention solves the problem of ambiguous data frames or ambiguous model predictions which can occur when the objects occlude each other, or a particular data frame is otherwise difficult or impossible to interpret The model follows the most probable set of model states into the future, and any spurious paths will usually develop low probabilities in future data frames, while good (i.e. xe2x80x9ccorrectxe2x80x9d) model states continue to develop high probabilities of representing the new data frames, as they are detected. By following predictions from a reasonable number of points in state space, the analysis scales well with large amounts of detected data.